package org.cxy.sort;

import java.util.Arrays;

//插入排序
public class InsertSortDemo {
    public static void main(String[] args) {
        int[] arr = {5, 4, 8, 2, 1, 6, 7};
        
        System.out.println("原始数组: " + Arrays.toString(arr));
        
        int[] sortedArr = insertSort(arr);
        
        System.out.println("排序后数组: " + Arrays.toString(sortedArr));
    }

    /**
     * 插入排序：对整型数组进行升序排序
     * 原理：将数组分为“已排序”和“未排序”两部分，
     *      每次从未排序部分取出第一个元素，插入到已排序部分的正确位置。
     *
     * @param arr 待排序的数组（原地修改）
     * @return 已排序的数组
     */
    public static int[] insertSort(int[] arr) {
        // 外层循环：控制“未排序”部分的起始位置
        // i 从 1 开始，因为默认 arr[0] 是已排序部分的第一个元素
        for (int i = 1; i < arr.length; i++) {
            System.out.println("将 arr[" + i + "] = " + arr[i] + " 插入到左边已排序部分");

            // 内层循环：在已排序部分中为 arr[i] 找到合适的插入位置
            // j 从 i 开始，向前遍历（j > 0），逐步比较并交换
            for (int j = i; j > 0; j--) {
                // 如果前一个元素比当前元素大，说明顺序不对，需要交换
                if (arr[j - 1] > arr[j]) {
                    // 交换 arr[j-1] 和 arr[j]
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;

                    // 可选：打印交换过程
                    System.out.println("  交换: " + Arrays.toString(arr));
                } else {
                    // 如果 arr[j-1] <= arr[j]，说明已找到正确位置，无需继续往前比较
                    // 因为左边已经是有序的
                    break;
                }
            }
            System.out.println("第 " + i + " 轮结束: " + Arrays.toString(arr));
        }
        return arr;
    }
}